package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Stack;

/**
 * 请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/iIQa4I
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 🧑 ‍wanwei
 * @since 2022-11-09 11:11
 */
public class CM每日温度 {


    public static void main(String[] args) {

        int[] array = {30,40,50,60};
        int[] ints = dailyTemperatures(array);
        PrintUtil.print(ints);
    }


    /**
     * 记录升序 /降序规则
     * 升序时 index为1 降序或平滑时入栈 等待升序后比较值大小 填入相应的index
     *
     * 时间复杂度为 n;
     * 空间复杂度为 log n
     *
     * @param temperatures
     * @return
     */
    public static int[] dailyTemperatures(int[] temperatures) {
        if(temperatures.length == 1){
            return new int[]{0};
        }
        Stack<Integer> stack = new Stack();
        int[] arrayIndex = new int[temperatures.length];

        for (int i = 1; i < arrayIndex.length; i++) {
            if(temperatures[i] > temperatures[i -1]){
                //升序
                arrayIndex[i - 1] = 1;
                while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                    //栈不为空 且栈顶元素小于当前指针值
                    int index = stack.pop();
                    arrayIndex[index] = i - index;
                }
            }else {
                //非升序
                stack.push(i -1);
            }
        }
        return arrayIndex;
    }
}
